04 Cokolada

Na omotu čokolade sa lešnikom piše da proizvođač garantuje da se u kvadratu od a * a kockica sigurno nalazi bar jedan lešnik. Nikola je kupio jednu čokoladu i zanima ga koji je najveći kvadrat koji može pronaći tako da se u njemu ne nalazi lešnik. Napisati program koji nalazi najveći kvadrat sačinjen od x * x kockica tako da ne sadrzi ni jedan lešnik. Vremenska složenost treba biti O(n²), a prostorna složenost O(n²).

Ulaz

Sa standardnog ulaza se učitava ceo broj n ( $1 n ^6 $), a zatim i n² brojeva (0 ili 1) koji predstavljaju da li određena kockica čokolade sadrži lešnik ili ne.

Izlaz

Ispisati jedan broj, koji predstavlja dužinu stranice najvećeg traženog kvadrata.

Primer

Ulaz

3
0 1 0
1 0 0
0 0 1

Izlaz

1

Primer

Ulaz

4
1 0 0 1
0 0 1 1
0 0 0 0
1 1 1 1

Izlaz

2